Algorithms and Models for the Web%2DGraph %2D 7th International Workshop

Text Classification through Time %2D Efficient Label Propagation in Time%2DBased Graphs.

Affiliation networks.
In the last decade, structural properties of several naturally arising networks (the Internet, social networks, the web graph, etc.) have been studied intensively with a view to understanding their evolution. In recent empirical work, Leskovec, Kleinberg, and Faloutsos identify two new and surprising properties of the evolution of many real-world networks: densification (the ratio of edges to vertices grows over time), and shrinking diameter (the diameter reduces over time to a constant). These properties run counter to conventional wisdom, and are certainly inconsistent with graph models prior to their work. In this paper, we present the first model that provides a simple, realistic, and mathematically tractable generative model that intrinsically explains all the well-known properties of the social networks, as well as densification and shrinking diameter. Our model is based on ideas studied empirically in the social sciences, primarily on the groundbreaking work of Breiger (1973) on bipartite models of social networks that capture the affiliation of agents to societies. We also present algorithms that harness the structural consequences of our model. Specifically, we show how to overcome the bottleneck of densification in computing shortest paths between vertices by producing sparse subgraphs that preserve or approximate shortest distances to all or a distinguished subset of vertices. This is a rare example of an algorithmic benefit derived from a realistic graph model. Finally, our work also presents a modular approach to connecting random graph paradigms (preferential attachment, edge-copying, etc.) to structural consequences (heavy-tailed degree distributions, shrinking diameter, etc.).
Secured and Lossless Watermarking Technique for Patent Infringement.

Corrigendum to %22efficient similarity search and classification via rank aggregation%22 by Ronald Fagin
In this corrigendum, we correct an error in the paper [1]. The error was discovered by Alexandr Andoni, and the corrected theorem is due to the three authors of [1], along with Alexandr Andoni and Mihai Pǎtra¸scu. Theorem 4 of [1] states: Let D be a collection of n points in R d. Let r1,... rm be random unit vectors in R d, where m = αɛ −2 log n with α suitably chosen. Let q ∈ R d be an arbitrary point, and define, for each i with 1 ≤ i ≤ m, the ranked list Li of the n points in D by sorting them in increasing order of their distances to the projection of q along ri. For each element x of D, let medrank(x) = median(L1(x),..., Lm(x)). Let z be a member of D such that medrank(z) is minimized. Then with probability at least 1−1/n, we have �z−q�2 ≤ (1+ɛ)�x−q�2 for all x ∈ D. As stated, the above theorem does not hold, but a version of it holds if one replaces the median over ranks by a median over suitably defined scores. Below, we give a counterexample to the original theorem, and then present our modification to the theorem, and the resulting algorithm. 1. A COUNTEREXAMPLE Intuitively, the above theorem does not hold in the following situation. Suppose q is the query point, p is the nearest neighbor of q, and z is at distance (1 + ɛ)�p − q�2. For a random unit vector r, let rankr(p) denote the rank of the point p in the list Lr of the set D of points sorted by their distance to the projection of q along r. While it is true that rankr(p) &lt; rankr(z) holds 1/2 + Ω(ɛ) fraction of the time (over the random choice of r), we cannot infer the same for the overall median rank when taking into the consideration the other points in D. In particular, a bad dataset is one where whenever rankr(p) &lt; rankr(z) then about half of the time both ranks are high, but when rankr(p)&gt; rankr(z) the Copyright is held by the author/owner(s).

Video suggestion and discovery for youtube taking random walks through the view graph.


Communication Lower Bounds Via the Chromatic Number.

Programmable clustering.
As network routers evolve towards supporting ever more higher-level networking functions beyond traditional network-layer and transport-layer protocols, programmability becomes a major design issue in network device OS (NDOS), which until very recently has been based on the type of OS used in embedded systems. On the other hand, it is now possible to build high-performance Internet routers from off-the-shelf PC-class hardware, particularly with the use of clustering technology. The goal of the Suez project is to build a cluster-based Internet router using generalpurpose processors as input/output link controllers and packet schedulers, and a Gigabit/sec system area network as the switching fabric. This paper presents the design and initial implementation of the Suez OS, which features scalable real-time packet scheduling, cache-conscious routing-table lookup, intra-cluster distributed buffer memory management, and a highly efficient kernel extension mechanism for active networking usin...
On the Hardness of Approximating Multicut and Sparsest%2DCut.
We show that the MULTICUT, SPARSEST-CUT, and MIN-2CNF ≡ DELETION problems are NP-hard to approximate within every constant factor, assuming the Unique Games Conjecture of Khot [STOC, 2002]. A quantitatively stronger version of the conjecture implies inapproximability factor of Ω(log log n). 1.
Comparing Partial Rankings.
Abstract. We provide a comprehensive picture of how to compare partial rankings, that is, rankings that allow ties. We propose several metrics to compare partial rankings and prove that they are within constant multiples of each other. Key words. partial ranking, bucket order, permutation, metric AMS subject classifications. 06A06, 68R99 DOI. 10.1137/05063088X
On the Hardness of Approximating Multicut and Sparsest%2DCut.
We show that the MULTICUT, SPARSEST-CUT, and MIN-2CNF ≡ DELETION problems are NP-hard to approximate within every constant factor, assuming the Unique Games Conjecture of Khot [STOC, 2002]. A quantitatively stronger version of the conjecture implies inapproximability factor of Ω(log log n). 1.
Exploiting anarchy in networks a game%2Dtheoretic approach to combining fairness and throughput.

Unweaving a web of documents.

Multi%2Dstructural databases.
This report has been submitted for publication outside of IBM and will Probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its coctents. In view of the transfer of copyright tti the outside publisher, its distribution Cutside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties).
Efficient Implementation of Large%2DScale Multi%2DStructural Databases.
In earlier work, we defined &#034;multi-structural  databases,&#034; a data model to support efficient analysis  of large, complex data sets over multiple numerical  and hierarchical dimensions. We defined  three types of queries over this data model, each of  which required solving an optimization problem.
Framework and algorithms for trend analysis in massive temporal data sets.

A mechanism for equitable bandwidth allocation under QoS and budget constraints.

A graph%2Dtheoretic approach to extract storylines from search results.

Comparing and Aggregating Rankings with Ties.
Rank aggregation has recently been proposed as a useful abstraction that has several applications,  including meta-search, synthesizing rank functions from multiple indices, similarity search, and classification.
An information statistics approach to data stream and communication complexity.
We present a new method for proving strong lower bounds in communication complexity.
Efficient similarity search and classification via rank aggregation.
We propose a novel approach to performing efficient similarity search  and classification in high dimensional data. In this framework, the database elements are vectors in a Euclidean space. Given a query vector in the same space, the goal is to find elements of the database that are similar to the query. In our approach, a small number of independent &#034;voters&#034; rank the database elements based on similarity to the query. These rankings are then combined by a highly efficient aggregation algorithm. Our methodology leads both to techniques for computing approximate nearest neighbors and to a conceptually rich alternative to nearest neighbors.
Comparing top k lists.
Motivated by several applications, we introduce various distance measures between “top k lists.” Some of these distance measures are metrics, while others are not. For each of these latter distance measures, we show that they are “almost ” a metric in the following two seemingly unrelated aspects: (i) they satisfy a relaxed version of the polygonal (hence, triangle) inequality, and (ii) there is a metric with positive constant multiples that bound our measure above and below. This is not a coincidence—we show that these two notions of almost being a metric are formally identical. Based on the second notion, we define two distance measures to be equivalent if they are bounded above and below by constant multiples of each other. We thereby identify a large and robust equivalence class of distance measures. Besides the applications to the task of identifying good notions of (dis-)similarity between two top k lists, our results imply polynomial-time constant-factor approximation algorithms for the rank aggregation problem [DKNS01] with respect to a large class of distance measures. To appear in SIAM J. on Discrete Mathematics. Extended abstract to appear in 2003 ACM-SIAM Symposium on Discrete Algorithms (SODA ’03).
Two applications of information complexity.
We show the following new lower bounds in two concrete complexity models:  (1) In the two-party communication complexity model, we show that the tribes function on n inputs [6] has two-sided error randomized complexity # n), while its nondeterminstic complexity and co-nondeterministic complexity are both #( # n). This separation between randomized and nondeterministic complexity is the best possible and it settles an open problem in Kushilevitz and Nisan [17], which was also posed by Beame and Lawry [5].
Searching the workplace web.
The social impact from the World Wide Web cannot be underestimated, but technologies used to build the Web are also revolutionizing the sharing of business and government information within intranets. In many ways the lessons learned from the Internet carry over directly to intranets, but others do not apply. In particular, the social forces that guide the development of intranets are quite di#erent, and the determination of a &#034;good answer&#034; for intranet search is quite di#erent than on the Internet. In this paper we study the problem of intranet search. Our approach focuses on the use of rank aggregation, and allows us to examine the e#ects of di#erent heuristics on ranking of search results.
Link Evolution Analysis and Algorithms.
Abstract. We anticipate that future web search techniques will exploit changes in web structure and content. As a first step in this direction, we examine the problem of integrating observed changes in link structure into static hyperlink-based ranking computations. We present a very efficient algorithm to incrementally compute good approximations to Google’s PageRank [Brin and Page 98], as links evolve. Our experiments reveal that this algorithm is both fast and yields excellent approximations to PageRank, even in light of large changes to the link structure. Our algorithm derives intuition and partial justification from a rigorous sensitivity analysis of Markov chains. Consider a regular Markov chain with stationary probability π, and suppose the transition probability into a state j is increased. We prove that this can only cause • πj to increase–adding a link to a site can only cause the stationary probability of the target site to increase; • the rank of j to improve–if the states are ordered according to their stationary probabilities, then adding a link to a site can only cause the rank of the target site to improve. This analysis formalizes why the intuition that drives Google never fails. 1.
Link Evolution Analysis and Algorithms.
Abstract. We anticipate that future web search techniques will exploit changes in web structure and content. As a first step in this direction, we examine the problem of integrating observed changes in link structure into static hyperlink-based ranking computations. We present a very efficient algorithm to incrementally compute good approximations to Google’s PageRank [Brin and Page 98], as links evolve. Our experiments reveal that this algorithm is both fast and yields excellent approximations to PageRank, even in light of large changes to the link structure. Our algorithm derives intuition and partial justification from a rigorous sensitivity analysis of Markov chains. Consider a regular Markov chain with stationary probability π, and suppose the transition probability into a state j is increased. We prove that this can only cause • πj to increase–adding a link to a site can only cause the stationary probability of the target site to increase; • the rank of j to improve–if the states are ordered according to their stationary probabilities, then adding a link to a site can only cause the rank of the target site to improve. This analysis formalizes why the intuition that drives Google never fails. 1.
On Polynomial%2DFactor Approximations to the Shortest Lattice Vector Length.

Comparing Top k Lists.
Motivated by several applications, we introduce various distance measures between “top k lists.” Some of these distance measures are metrics, while others are not. For each of these latter distance measures, we show that they are “almost ” a metric in the following two seemingly unrelated aspects: (i) they satisfy a relaxed version of the polygonal (hence, triangle) inequality, and (ii) there is a metric with positive constant multiples that bound our measure above and below. This is not a coincidence—we show that these two notions of almost being a metric are formally identical. Based on the second notion, we define two distance measures to be equivalent if they are bounded above and below by constant multiples of each other. We thereby identify a large and robust equivalence class of distance measures. Besides the applications to the task of identifying good notions of (dis-)similarity between two top k lists, our results imply polynomial-time constant-factor approximation algorithms for the rank aggregation problem [DKNS01] with respect to a large class of distance measures. To appear in SIAM J. on Discrete Mathematics. Extended abstract to appear in 2003 ACM-SIAM Symposium on Discrete Algorithms (SODA ’03).
An Information Statistics Approach to Data Stream and Communication Complexity.
We present a new method for proving strong lower bounds in communication complexity.
Algorithmic Derandomization via Complexity Theory.

Sampling Short Lattice Vectors and the Closest Lattice Vector Problem.
We present a 2^{O(n)} time Turing reduction from the closest lattice vector problem to the shortest lattice vector problem. Our reduction assumes access to a subroutine that solves SVP exactly and a subroutine to sample short vectors from a lattice, and computes a (1+ epsilon)-approximation to CVP. As a consequence, using the SVP algorithm from [1], we obtain a randomized 2^{O(1+epsilon^-1)n} algorithm to obtain a (1+epsilon)-approximation for the closest lattice vector problem in n dimensions. This improves the existing time bound of O(n!) for CVP (achieved by a deterministic algorithm in [2]).
Information Theory Methods in Communication Complexity.
We use tools and techniques from information theory to study communication complexity problems in the one-way and simultaneous communication models. Our results include: (1) A tight characterization of multi-party one-way communication complexity for product distributions in terms of VC-dimension and shatter coefficients; (2) An equivalence of multi-party one-way and simultaneous communication models for product distributions; (3) A suite of lower bounds for specific functions in the simultaneous communication model, most notably an optimal lower bound for the multi-party set disjointness problem of Alon et al. [AMS99] and for the generalized addressing function problem of Babai et al. [BGKL96] for arbitrary groups. Methodologically, our main contribution is rendering communication complexity problems in the framework of information theory. This allows us access to the powerful calculus of information theory and the use of fundamental principles such as Fano&#039;s inequality and the Maximum Likelihood Estimate Principle.
Counting Distinct Elements in a Data Stream.
We present three algorithms to count the number of distinct elements in a data stream to within a factor of 1 &amp;plusmn; epsilon. Our algorithms improve upon known algorithms for this problem, and offer a spectrum of time/space tradeoffs.
Reductions in streaming algorithms
We introduce reductions in the streaming model as a tool in the design of streaming algorithms. We develop the concept of list-efficient streaming algorithms that are essential to the design of efficient streaming algorithms through reductions. Our results include a suite of list-efficient streaming algorithms for basic statistical primitives. Using the reduction paradigm along with these tools, we design streaming algorithms for approximately counting the number of triangles in a graph presented as a stream. A specific highlight of our work is the first algorithm for the number of distinct elements in a data stream that achieves arbitrary approximation factors. (Independently, Trevisan [Tre01] has solved this problem via a different approach; our algorithm has the advantage of being list-efficient.)
Approximate counting of inversions in a data stream.
Abstract Inversions are used as a fundamental quantity to measure the sortedness of data, to evaluate different ranking methods for databases, and in the context of rank aggregation. Considering the volume of the data sets in these applications, the data stream model [16, 2] is a natural setting to design efficient algorithms. We obtain a suite of space-efficient streaming algorithms for approximating the number of inversions in a permutation to within a factor of ffl. The best space bound we achieve for this problem is O(log n log log n) through a deterministic algorithm. In contrast, we derive an \Omega (n) lower bound for randomized exact computation for this problem; thus approximation is essential. For the more general problem of approximating the number of inversions between two permutations, we obtain a randomized O(pn log n)-space algorithm. For approximating the number of inversions in a general list, we give a randomized O(pn log2 n)-space two-pass algorithm. In contrast, we derive \Omega (n) lower bounds for deterministic approximate computation for these problems; thus randomization is essential. All our algorithms use only O(log n) time per data item.
Algorithmic derandomization via complexity theory.

Self%2Dsimilarity in the web.
 
An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem.

On polynomial approximation to the shortest lattice vector length.
We obtain a 2  O(n=ffl)  time algorithm to approximate the length of the shortest vector in an  n-dimensional lattice to within a factor of n  3+ffl  . In this note we consider the complexity of approximating the shortest lattice vector length (called SVP-Length) when the approximation factor is poly(n). An obvious candidate for producing polynomial approximations to SVP-Length --- Schnorr&#039;s improvement of the Lov&#039;asz basis reduction algorithm [6] --- turns out to be uninteresting: Schnorr&#039;s algorithm takes O(n  2  (k  k=2+o(k)  + n  2  )) arithmetic steps (on polynomial-sized operands) to produce a (  p  6k)  n=k  approximation. To obtain poly(n) approximation factors, k = \Omega\Gamma n), so the running time is 2\Omega\Gamma  n log n)  , which is pointless in the light of an O(n  n  ) algorithm to solve it exactly [5]. We show:  Theorem 1 There exists an absolute constant fl ? 1 such that for any ffl ? 0, SVP-Length can be approximated to within n  3+ffl  in probabilistic time 2  fln(  1 2 +  1  ffl )  . Proof. Our algorithm uses Ajtai&#039;s [1] reduction of SVP-Length to the problem of finding a short vector in a special class of lattices; we solve the latter problem by adapting an idea of Blum, Kalai, and Wasserman [2]. To obtain the best approximation factors, we use the sharpest form of the reduction, due to Cai and Nerurkar [4, 3]. For integers n; m; and q, Ajtai [1] defines a family of lattices in Z  m  defined by (n; m; q) =  fL(A)g, where A is an n \Theta m matrix over Z q , and L(A) = fx 2 Z  m  j Ax j 0(mod q)g. The main result of [1] is that if there is an algorithm A that, with certain settings of q and m, computes a non-zero vector of length n in a random lattice from (n; m; q) with non-negligible probability, then there is a randomized algorithm B that compu...
Sampling algorithms lower bounds and applications.
]  Ziv Bar-Yossef  y  Computer Science Division  U. C. Berkeley  Berkeley, CA 94720  zivi@cs.berkeley.edu  Ravi Kumar  IBM Almaden  650 Harry Road  San Jose, CA 95120  ravi@almaden.ibm.com  D. Sivakumar  IBM Almaden  650 Harry Road  San Jose, CA 95120  siva@almaden.ibm.com  ABSTRACT  We develop a framework to study probabilistic sampling algorithms that approximate general functions of the form f : A  n  ! B, where A and B are arbitrary sets. Our goal is to obtain lower bounds on the query complexity of functions, namely the number of input variables x i that any sampling algorithm needs to query to approximate f(x1 ; : : : ; xn ).  We define two quantitative properties of functions --- the block sensitivity and the minimum Hellinger distance --- that give us techniques to prove lower bounds on the query complexity. These techniques are quite general, easy to use, yet powerful enough to yield tight results. Our applications include the mean and higher statistical moments, the median and other selection functions, and the frequency moments, where we obtain lower bounds that are close to the corresponding upper bounds.  We also point out some connections between sampling and streaming algorithms and lossy compression schemes.  1. 
A sieve algorithm for the shortest lattice vector problem.
We present a randomized 2  O(n)  time algorithm to compute the shortest non-zero vector in an  n-dimensional rational lattice. The best known time upper bound for this problem was 2  O(n log n)  first given by Kannan [6] in 1983. We obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.  1 
Self%2Dsimilarity in the Web.
 
On the unique shortest lattice vector problem.
We give a simplified proof of a theorem of Lagarias, Lenstra and Schnorr [17] that the problem of approximating the length of the shortest lattice vector within a factor of Cn,  for an appropriate constant C, cannot be NP-hard, unless NP = coNP. We also prove that the problem of findng a n  1=4  -unique shortest lattice vector is not NP-hard under polynomial time many-one reductions, unless the polynomial time hierarchy collapses. 1 Introduction  A discrete additive subgroup of R  n  is called a lattice. Recently in a beautiful paper Ajtai [1] established the first explicit connection between, in a certain technical sense, the worst-case and the average-case complexity of the shortest lattice vector problem. This is the problem of finding or approximating the shortest lattice vector or its length. In a tour de force, Ajtai [2] further established the NP-hardness of the problem of finding the shortest lattice vector (in Euclidean norm, or l 2 -norm), as well as the problem of approximat...
Rank aggregation methods for the Web.
We consider the problem of combining ranking results from various sources. In the context of the Web, the main applications include building meta-search engines, combining ranking functions, selecting documents based on multiple criteria, and improving search precision through word associations. Wedevelop a set of techniques for the rank aggregation problem and compare their performance to that of well-known methods. A primary goal of our work is to design rank aggregation techniques that can effectively combat &#034;spam,&#034; a serious problem in Web searches. Experiments show that our methods are simple, efficient, and effective.  Keywords: rank aggregation, ranking functions, metasearch, multi-word queries, spam  1. 
On the unique shortest lattice vector problem.
We give a simplified proof of a theorem of Lagarias, Lenstra and Schnorr [17] that the problem of approximating the length of the shortest lattice vector within a factor of Cn,  for an appropriate constant C, cannot be NP-hard, unless NP = coNP. We also prove that the problem of findng a n  1=4  -unique shortest lattice vector is not NP-hard under polynomial time many-one reductions, unless the polynomial time hierarchy collapses. 1 Introduction  A discrete additive subgroup of R  n  is called a lattice. Recently in a beautiful paper Ajtai [1] established the first explicit connection between, in a certain technical sense, the worst-case and the average-case complexity of the shortest lattice vector problem. This is the problem of finding or approximating the shortest lattice vector or its length. In a tour de force, Ajtai [2] further established the NP-hardness of the problem of finding the shortest lattice vector (in Euclidean norm, or l 2 -norm), as well as the problem of approximat...
Random graph models for the web graph.

The Web as a Graph.
The pages and hyperlinks of the World-Wide Web maybe  viewed as nodes and edges in a directed graph. This graph has about a billion nodes today,several billion links, and appears to grow exponentially with time. There are many reasons---mathematical, sociological, and commercial---for studying the evolution of this graph. We first review a set of algorithms that operate on the Web graph, addressing problems from Web search, automatic community discovery, and classification. We then recall a number of measurements and properties of the Web graph. Noting that traditional random graph models do not explain these observations, we propose a new family of random graph models.
Self%2DTesting without the Generator Bottleneck.
Suppose P is a program designed to compute a function f defined on a group G. The task of self-testing P , that is, testing if P computes f correctly on most inputs, usually involves testing explicitly if P computes f correctly on every generator of G. In the case of multivariate functions, the number of generators, and hence the number of such tests, becomes prohibitively large. We refer to this problem as the generator bottleneck . We develop a technique that can be used to overcome the generator bottleneck for functions that have a certain nice structure, specifically if the relationship between the values of the function on the set of generators is easily checkable. Using our technique, we build the first efficient self-testers for many linear, multilinear, and some non-linear functions. This includes the FFT, and various polynomial functions. All of the self-testers we present make only O(1) calls to the program that is being tested. As a consequence of our techniques, we also obtain efficient program result-checkers for all these problems.
A Generalization of Resource%2DBounded Measure
siamltex
Resolution of Hartmanis%27 conjecture for NL%2Dhard sparse sets.
en a graph G and a pair of vertices s; t, this reduction produces a polynomial number of graphs G 1 ; : : : ; G k of polynomial size, together with distinguished vertex-pairs (s 1 ; t 1 ); : : : ; (s k ; t k ), that satisfy the following conditions. If there is no path from s to t in G, then no G i has a path from s i  to t i ; if there is a path from s to t in G, then with high probability, at least one of the G i &#039;s has a unique path from s i to t i . This reduction is due to Avi Wigderson [Wig94], and it exploits the &#034;isolation lemma&#034; of Mulmuley, Vazirani and Vazira
A Note on the Shortest Lattice Vector Problem.
We show that the problem of deciding whether a given rational lattice L has a vector of  length less than some given value r is NP-hard, even under the promise that L has exactly zero  or one vector of length less than r.
Proofs%2C Codes%2C and Polynomial%2DTime Reducibilities.
We show how to construct proof systems for NP languages where a deterministic polynomialtime  verifier can check membership, given any N  (2=3)+ffl  bits of an N -bit witness of membership.
Roundness Estimation via Random Sampling.
We present an efficient probabilistic algorithm to estimate the  roundness of a convex object on the plane. The probing model we use, that is, the type of access the algorithm has to the object, was defined by Cole and Yap [CY87], and is related to physical devices employed in computational metrology. This algorithm is not only simple but also very different from and more efficient than previous algorithms for this problem [Swa93, LL91, EFNN89, MSY97]. Our analysis involves proving sharp versions of the planar isoperimetric inequality and using them in conjunction with results from geometric probability.
On the Hardness of Permanent.
. We prove that if there is a polynomial time algorithm which computes the permanent of a matrix of order n for any inverse polynomial fraction of all inputs, then there is a BPP algorithm computing the permanent for every matrix. It follows that this hypothesis implies P  #P  = BPP. Our algorithm works over any sufficiently large finite field (polynomially larger than the inverse of the assumed success ratio), or any interval of integers of similar range. The assumed algorithm can also be a probabilistic polynomial time algorithm. Our result is essentially the best possible based on any black box assumption of permanent solvers, and is a simultaneous improvement of the results of Gemmell and Sudan [GS92], Feige and Lund [FL92] as well as Cai and Hemachandra [CH91], and Toda (see [ABG90]). 1 Introduction  The permanent of an n \Theta n matrix A is defined as per(A) =  X  oe2Sn n  Y  i=1  A i;oe(i) ; where Sn is the symmetric group on n letters, i.e., the set of all permutations of  f1;...
Hardness and Hierarchy Theorems for Probabilistic Quasi%2DPolynomial Time.
We prove tight hierarchy theorems for bounded error probabilistic quasi-polynomial time classes, under several hardness assumptions. We show that assuming either (1) the Permanent does not have a subexponential time BP algorithm, or (2) some function in EXPTIME does not have subexponential size circuits, then for every 1  ff ! fi, BPTIME(2  (log n)  ff  ) $ BPTIME(2  (log n)  fi  ):   Department of Computer Science, State University of New York at Buffalo, Buffalo, NY 14260. Email:  cai@cs.buffalo.edu. Research supported in part by NSF grant CCR-9634665 and a J. S. Guggenheim Fellowship.   y  Department of Computer Science, State University of New York at Buffalo, Buffalo, NY 14260. Email:  apn@cs.buffalo.edu. Research supported in part by NSF grant CCR-9634665.  z  Department of Computer Science, University of Houston, Houston, TX 77204. Email: siva@cs.uh.edu. Research supported in part by NSF CAREER award CCR-9734164.  1 Introduction  It has been observed for some time now that the ...
Sparse Hard Sets for P Resolution of a Conjecture of Hartmanis.
Building on a recent breakthrough by Ogihara, we resolve a conjecture made by Hartmanis in 1978 regarding the (non-) existence of sparse sets complete for P under logspace many-one reductions. We show that if there exists a sparse hard set for P under logspace many-one reductions, then P = LOGSPACE. We further prove that if P has a sparse hard set under many-one reductions computable in NC  1  , then P collapses to NC  1  .
On Membership Comparable Sets.
A set A is k(n) membership comparable if there is a polynomial time computable  function that, given k(n) instances of A of length at most n, excludes one of the  2  k(n)  possibilities for the memberships of the given strings in A. We show that if  SAT is O(log n) membership comparable, then UniqueSAT 2 P. This extends the  work of Ogihara; Beigel, Kummer, and Stephan; and Agrawal and Arvind [Ogi94,  BKS94, AA94], and answers in the affirmative an open question suggested by Buhrman,  Fortnow, and Torenvliet [BFT97]. Our proof also shows that if SAT is o(n) membership  comparable, then UniqueSAT can be solved in deterministic time 2  o(n)  . Our main  technical tool is an algorithm of Ar et al. [ALRS92] to reconstruct polynomials from  noisy data through the use of bivariate polynomial factorization.
Probabilistic Martingales and BPTIME Classes.
We define probabilistic martingales based on randomized approximation schemes, and show that the resulting notion of probabilistic measure has several desirable robustness properties. Probabilistic martingales can simulate the &#034;betting games&#034; of [BMR  +  98], and can cover the same class that a &#034;natural proof &#034; diagonalizes against, as implicitly already shown in [RSC95]. The notion would become a full-fledged measure on bounded-error complexity classes such as BPP and BPE if it could be shown to satisfy the &#034;measure conservation&#034; axiom of [Lut92] for these classes. We give a sufficient condition in terms of simulation by &#034;decisive&#034; probabilistic martingales that implies not only measure conservation, but also a much tighter bounded error probabilistic time hierarchy than is currently known. In particular it implies BPTIME[O(n)] 6= BPP, which would stand in contrast to recent claims of an oracle  A giving BPTIME  A  [O(n)] = BPP  A  . This paper also makes new contributions to the problem of defining (deterministic) measure on P and other sub-exponential classes. 1 
On Membership Comparable Sets.
A set A is k(n) membership comparable if there is a polynomial time computable  function that, given k(n) instances of A of length at most n, excludes one of the  2  k(n)  possibilities for the memberships of the given strings in A. We show that if  SAT is O(log n) membership comparable, then UniqueSAT 2 P. This extends the  work of Ogihara; Beigel, Kummer, and Stephan; and Agrawal and Arvind [Ogi94,  BKS94, AA94], and answers in the affirmative an open question suggested by Buhrman,  Fortnow, and Torenvliet [BFT97]. Our proof also shows that if SAT is o(n) membership  comparable, then UniqueSAT can be solved in deterministic time 2  o(n)  . Our main  technical tool is an algorithm of Ar et al. [ALRS92] to reconstruct polynomials from  noisy data through the use of bivariate polynomial factorization.
A Generalization of Resource%2DBounded Measure
siamltex
A Generalization of Resource%2DBounded Measure
siamltex
A Generalization of Resource%2DBounded Measure
siamltex
Resolution of Hartmanis%27 Conjecture for NL%2DHard Sparse Sets.
en a graph G and a pair of vertices s; t, this reduction produces a polynomial number of graphs G 1 ; : : : ; G k of polynomial size, together with distinguished vertex-pairs (s 1 ; t 1 ); : : : ; (s k ; t k ), that satisfy the following conditions. If there is no path from s to t in G, then no G i has a path from s i  to t i ; if there is a path from s to t in G, then with high probability, at least one of the G i &#039;s has a unique path from s i to t i . This reduction is due to Avi Wigderson [Wig94], and it exploits the &#034;isolation lemma&#034; of Mulmuley, Vazirani and Vazira
Constant Depth Circuits and the Lutz Hypothesis.
Resource-bounded measure theory [7] is a study of complexity classes via an adaptation of  the probabilistic method. The central hypothesis in this theory is the assertion that NP does  not have measure zero in Exponential Time. This is a quantitative strengthening of NP 6= P.
Efficient Self%2DTesting%2FSelf%2DCorrection of Linear Recurrences.
We consider the problem of designing self-testers/selfcorrectors for functions defined by linear recurrences. We present the first complete package of efficient and simple self-testers, self-correctors, and result-checkers for such functions. The results are proved by demonstrating an efficient reduction from this problem to the problem of testing linear functions over certain matrix groups. Our tools include spectral analysis of matrices over finite fields, and various counting arguments that extend known techniques. The matrix twist yields simple and efficient self-testers for all linear recurrences. We also show a technique of using convolution identities to obtain very simple self-testers and selfcorrectors. Our techniques promise new and efficient ways of testing VLSI chips for applicationsin control engineering, signal processing, etc.
On the Existence of Hard Sparse Sets under Weak Reductions.
Recently a 1978 conjecture by Hartmanis [Har78] was resolved [CS95], following progress made by [Ogi95]. It was shown that there is no sparse set that is hard for P under logspace many-one reductions, unless P = LOGSPACE. We extend the results to the case of sparse sets that are hard under more general reducibilities. Our main results are as follows. (1) If there exists a sparse set that is hard for P under bounded truth-table reductions, then P = NC  2  . (2) If there exists a sparse set that is hard for P under randomized logspace reductions with one-sided error, then P = Randomized LOGSPACE. (3) If there exists an NP-hard sparse set under randomized polynomial-time reductions with one-sided error, then NP = RP. (4) If there exists a 2  (log n)  O(1)  -sparse hard set for P under truth-table reductions, then P ` DSPACE[(logn)  O(1)  ]. As a by-product of (4), we obtain a uniform O(log  2  n log log n) time parallel algorithm for computing the rank of a 2  log  2  n  \Theta n matrix o...
Pseudorandom Generators%2C Measure Theory%2C and Natural Proofs.
 We prove that if strong pseudorandom number generators exist, then the class of languages that have polynomialsized circuits (P/poly) is not measurable within exponential time, in terms of the resource-bounded measure theory of Lutz. We prove our result by showing that if P/poly has measure zero in exponential time, then there is a natural proof against P/poly, in the terminology of Razborov and Rudich [25]. We also provide a partial converse of this result. 
The Resolution of a Hartmanis Conjecture.
Building on the recent breakthrough by Ogihara, we resolve a conjecture made by Hartmanis in 1978 regarding the (non) existence of sparse sets complete for P under logspace many-one reductions. We show that if there exists a sparse hard set for P under logspace many-one reductions, then P = LOGSPACE. We further prove that if P has a sparse hard set under many-one reductions computable in NC  1  , then P collapses to NC  1  .  1 Introduction  A set S is called sparse if there are at most a polynomial number of strings in S up to length  n. Sparse sets have been the subject of study in complexity theory for the past 20 years, as they reveal inherent structure and limitations of computation [BH77, HOW92, You92a, You92b]. For instance, it is well known that the class of languages polynomial time Turing reducible (i.e. by Cook reductions) to a sparse set is precisely the class of languages with polynomial size circuits. One major motivation for the study of sparse sets, and various reducib...
On Self%2DTesting without the Generator Bottleneck.
Suppose P is a program designed to compute a function f defined on a group G. The task of self-testing P , that is, testing if P computes f correctly on most inputs, usually involves testing explicitly if P computes f correctly on every generator of G. In the case of multivariate functions, the number of generators, and hence the number of such tests, becomes prohibitively large. We refer to this problem as the generator bottleneck . We develop a technique that can be used to overcome the generator bottleneck for functions that have a certain nice structure, specifically if the relationship between the values of the function on the set of generators is easily checkable. Using our technique, we build the first efficient self-testers for many linear, multilinear, and some non-linear functions. This includes the FFT, and various polynomial functions. All of the self-testers we present make only O(1) calls to the program that is being tested. As a consequence of our techniques, we also obtain efficient program result-checkers for all these problems.
Communication Complexity of Key Agreement on Small Ranges.

Pseudorandom Generators%2C Measure Theory%2C and Natural Proofs
 We prove that if strong pseudorandom number generators exist, then the class of languages that have polynomialsized circuits (P/poly) is not measurable within exponential time, in terms of the resource-bounded measure theory of Lutz. We prove our result by showing that if P/poly has measure zero in exponential time, then there is a natural proof against P/poly, in the terminology of Razborov and Rudich [25]. We also provide a partial converse of this result. 
On Quasilinear%2DTime Complexity Theory.
This paper furthers the study of quasilinear time complexity initiated by  Schnorr and Gurevich and Shelah. We show that the fundamental properties  of the polynomial-time hierarchy carry over to the quasilinear-time hierarchy.
Quasilinear Time Complexity Theory.
This paper furthers the study of quasilinear time complexity initiated by  Schnorr and Gurevich and Shelah. We show that the fundamental properties  of the polynomial-time hierarchy carry over to the quasilinear-time hierarchy.
